#include <stdio.h>
#include <stdlib.h>

#define infinity 10000  /* 表示没有关系的常数 */
#define kMaxM 100000    /* 关系条数最大值 */
typedef enum { false, true } bool;

/* 集合相关定义与操作 */
#define kMaxSize 100000   /* 集合最大元素个数 */
typedef int SElemSet; /* 默认元素用非负整数表示 */
typedef SElemSet SetName; /* 默认用根结点的下标作为集合名称 */
typedef struct SetNode {
    SElemSet parent; /* 父结点 */
    int size; /* 群规模 */
    int rank; /* 秩，用于最小生成树 */
    SetName name; /* 集合名称，即朋友群的编号 */
    int strength; /* 凝聚力 */
    bool root; /* 是否原始集合的根结点 */
} Set[kMaxSize + 1]; /* 假设集合元素下标从1开始 */

void InitSet(Set set, int n); /* 初始化集合 */
SetName Find(Set set, SElemSet x); /* 找到x所在集合的根结点 */
void UnionPersons(Set set, SElemSet x, SElemSet y,
                  int strength); /* 合并两个人进同一个群 */
/* 集合相关定义与操作 结束 */

/* 边集相关定义与操作 */
typedef int Vertex; /* 顶点 */
typedef struct EdgeNode { /* 边 */
    Vertex u, v; /* 边(u,v)的两个端点 */
    int weight; /* 权重 */
} Edge[kMaxM];

int CmpWeight(const void *a, const void *b); /* qsort比较函数 */
/* 边集相关定义与操作 结束*/

/* 最小生成树相关函数 */
bool IsCycle(Set v, Vertex v1,
             Vertex v2); /* 判断边(v1, v2)的加入是否构成回路 */
int Kruskal(Set v, Edge e, int n_verts,
            int m_edges); /* Kruskal 求最小生成树算法 */
/* 最小生成树相关函数 结束*/

int ReadRelations(Set v, Edge e, int m); /* 读取输入，建群和边集 */
int GetGroups(Set v, int
              n); /* 统计有多少个群，并修正单人群的凝聚力 */
int CmpSet(const void *a, const void *b); /* qsort比较函数 */
void OutputGroups(Set v, int n); /* 输出群信息 */

int main(void) {
    int n, m, n_verts, m_edges, mst_weight;
    Set v; /* 顶点集合 */
    Edge e; /* 边集合 */

    scanf("%d %d", &n, &m);
    InitSet(v, n); /* 顶点集合初始化 */
    m_edges = ReadRelations(v, e, m); /* 根据输入建群，并获得边 */
    n_verts = GetGroups(v, n); /* 将一个群缩成一个顶点 */
    mst_weight = Kruskal(v, e, n_verts, m_edges); /* 求最小生成树 */
    OutputGroups(v, n); /* 输出群信息 */
    printf("%d\n", mst_weight); /* 输出最小生成树权重 */

    return 0;
}

void InitSet(Set set, int n) {
    /* 初始化集合 */
    SElemSet x;

    for (x = 1; x <= n; x++) {
        set[x].parent = x; /* x为根结点 */
        set[x].size = 1; /* 集合只有1个元素 */
        set[x].rank = 0; /* 秩的初始值 */
        set[x].name = x; /* 群编号是自己 */
        set[x].strength = infinity; /* 凝聚力初始值 */
        set[x].root = true; /* x为根结点 */
    }
}

SetName Find(Set set, SElemSet x) {
    /* 找到x所在集合的根结点 */
    if (x != set[x].parent) {
        set[x].parent = Find(set, set[x].parent);
    }
    return set[x].parent;
}

void UnionPersons(Set set, SElemSet x, SElemSet y, int strength) {
    /* 合并两个人进同一个群 */
    SetName i, j, t;

    i = Find(set, x);
    j = Find(set, y);
    if (i != j) {
        if (set[i].size < set[j].size) {
            t = i;
            i = j;
            j = t; /* 交换i和j的值 */
        } /* 此处保证set[i]比set[j]人多 */
        set[j].parent = i; /* 合并两个集合，i成为新的根 */
        set[j].root = false; /* j不再是根 */
        set[i].size += set[j].size; /* 人数合并 */
        if (set[j].name < set[i].name) {
            set[i].name = set[j].name; /* 群编号取最小值 */
        }
        if (set[j].strength < set[i].strength) {
            set[i].strength = set[j].strength; /* 凝聚力取最小值 */
        }
    }
    if (strength < set[i].strength) {
        set[i].strength = strength; /* 凝聚力取最小值 */
    }
}

int CmpWeight(const void *a, const void *b) {
    /* qsort比较函数 */
    return ((const struct EdgeNode*)a)->weight
           < ((const struct EdgeNode*)b)->weight ?
           -1 : 1; /* 按权重的非递减序 */
}

bool IsCycle(Set set, Vertex v1, Vertex v2) {
    /* 判断边(v1, v2)的加入是否构成回路 */
    SetName i, j;
    bool ret = true; /* 默认构成回路 */

    i = Find(set, v1); /* 得到v1所属的连通集名称 */
    j = Find(set, v2); /* 得到v2所属的连通集名称 */
    if (i != j) {
        /* 不构成回路，团结两个群，即将两个连通集合并 */
        if (set[i].rank > set[j].rank) {
            set[j].parent = i;
        } else if (set[i].rank < set[j].rank) {
            set[i].parent = j;
        } else { /* set[i].rank == set[j].rank */
            set[i].parent = j;
            set[j].rank++;
        }
        ret = false; /* 不构成回路 */
    }
    return ret;
}

int Kruskal(Set v, Edge e, int n_verts, int m_edges) {
    /* Kruskal 求最小生成树算法 */
    int weight; /* 记录生成树权重 */
    int cnt_edge, i;

    /* 将所有边按权重的非递减序排序 */
    qsort(e, m_edges, sizeof(struct EdgeNode), CmpWeight);
    weight = (n_verts - 1) * infinity; /* 先假设所有群之间都没有关系 */
    cnt_edge = 0; /* 初始化边的计数器 */
    i = 0; /* 第一条边的下标 */
    while (cnt_edge < (n_verts - 1)) {
        /* 当收集的边不足以构成树时 */
        if (i == m_edges) { /* 边集已空 */
            break; /* 跳出循环 */
        }
        if (IsCycle(v, e[i].u, e[i].v) == false) {
            /* 若边e[i]的加入不构成回路 */
            weight = weight - infinity + e[i].weight; /* 收录e[i] */
            cnt_edge ++;
        }
        i++; /* 考察下一条边 */
    }
    return weight;
}

int ReadRelations(Set v, Edge e, int m) {
    /* 读取输入，构建原始集合 */
    int i, m_edges;
    Vertex v1, v2;
    int strength;

    m_edges = 0;
    for (i = 0; i < m; i++) {
        scanf("%d %d %d", &v1, &v2, &strength);
        if (strength > 0) { /* 正权重则合并两人所在的群 */
            UnionPersons(v, v1, v2, strength);
        } else { /* 负权重则记录成边 */
            e[m_edges].u = v1;
            e[m_edges].v = v2;
            e[m_edges].weight = -strength;
            m_edges++;
        }
    }
    return m_edges;
}

int GetGroups(Set v, int n) {
    /* 统计有多少个群，并修正单人群的凝聚力 */
    int i, n_verts;

    n_verts = 0;
    for (i = 1; i <= n; i++) {
        if (v[i].root == true) { /* i是根结点 */
            n_verts++; /* 一个集合缩成一个图顶点 */
            /* 孤独顶点的凝聚力为0 */
            if (v[i].strength == infinity)
                v[i].strength = 0;
        }
    }
    return n_verts;
}

int CmpSet(const void *a, const void *b) {
    /* qsort比较函数 */
    int k;
    k = ((const struct SetNode*)a)->strength
        > ((const struct SetNode*)b)->strength ?
        -1 : 1; /* 按凝聚力的非递增序 */
    if (((const struct SetNode *)a)->strength
    == ((const struct SetNode *)b)->strength) { /* 若凝聚力并列 */
        k = ((const struct SetNode*)a)->size
            > ((const struct SetNode*)b)->size ?
            -1 : 1; /* 按群规模的非递增序 */
        if (((const struct SetNode *)a)->size
        == ((const struct SetNode *)b)->size) { /* 若群规模并列 */
            k = ((const struct SetNode*)a)->name
                < ((const struct SetNode*)b)->name ?
                -1 : 1; /* 按群编号的增序 */
        }
    }
    return k;
}

void OutputGroups(Set v, int n) {
    /* 输出群信息 */
    int i;

    /* 将集合元素按凝聚力、规模、群编号排序 */
    qsort(v + 1, n, sizeof(struct SetNode), CmpSet);
    for (i = 1; i <= n; i++) { /* 找到第1个群 */
        if (v[i].root == true)
            break;
    }
    /* 第一个群输出时，左边无空格 */
    printf("%d-%d", v[i].name, v[i].strength);
    for (i++; i <= n; i++) { /* 继续输出剩余的群 */
        if (v[i].root == true)
            printf(" %d-%d", v[i].name, v[i].strength);
    }
    printf("\n");
}